﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Jayden.Dll.PathFinding;

namespace Jayden.Dll.PathFinding
{
	public abstract class AStarPathFinder : PathFinder
	{
		private class AStarPathNodeEntry : IComparable<AStarPathNodeEntry>
		{
			private AStarPathNodeEntry m_Origin;
			private PathNode m_Node;
			private PathInformation m_Path;
			private double m_Cost;
			private double m_EstimatedCost;

			public AStarPathNodeEntry(AStarPathNodeEntry origin, PathInformation path, PathNode node, double cost, double estimatedCost)
			{
				m_Path = path;
				m_Origin = origin;
				m_Node = node;
				m_Cost = cost;
				m_EstimatedCost = estimatedCost;
			}

			public AStarPathNodeEntry Origin { get { return m_Origin; } set { m_Origin = value; } }
			public PathNode Node { get { return m_Node; } }
			public PathInformation Path { get { return m_Path; } set { m_Path = value; } }
			public double Cost { get { return m_Cost; } set { m_Cost = value; } }
			public double EstimatedCost { get { return m_EstimatedCost; } }
			public double Score { get { return Cost + EstimatedCost; } }

			public override bool Equals(object obj)
			{
				if(obj is AStarPathNodeEntry)
					return m_Node.Equals((obj as AStarPathNodeEntry).Node);
				return false;
			}

			public override int GetHashCode() { return m_Node.GetHashCode(); }
			public int CompareTo(AStarPathNodeEntry other) { return Score.CompareTo(other.Score); }
		}

		private HashSet<AStarPathNodeEntry> m_OpenList;
		private HashSet<PathNode> m_ClosedList;
		private Dictionary<PathNode, AStarPathNodeEntry> m_Entries;

		public List<PathInformation> FindPath(PathNode start, PathNode end) { return FindPath(start, new PathNodeTarget(end)); }
		public List<PathInformation> FindPath(PathNode start, PathNodeCondition condition)
		{
			AStarPathNodeEntry startEntry = new AStarPathNodeEntry(null, null, start, 0, EstimatedMovementCost(start, condition));
			m_OpenList = new HashSet<AStarPathNodeEntry>();
			m_ClosedList = new HashSet<PathNode>();
			m_Entries = new Dictionary<PathNode, AStarPathNodeEntry>();

			m_OpenList.Add(startEntry);
			m_Entries.Add(startEntry.Node, startEntry);

			AStarPathNodeEntry endEntry = null;

			while (m_OpenList.Count > 0)
			{
				List<AStarPathNodeEntry> sortedList = new List<AStarPathNodeEntry>(m_OpenList);
				sortedList.Sort();
				AStarPathNodeEntry currentEntry = sortedList[0];
				if (condition.IsValidNode(currentEntry.Node))
				{
					endEntry = currentEntry;
					break;
				}
				m_OpenList.Remove(currentEntry);
				m_ClosedList.Add(currentEntry.Node);
				m_Entries.Remove(currentEntry.Node);
				foreach (PathInformation information in currentEntry.Node.Paths)
				{
					PathNode node = information.End;
					if (m_ClosedList.Contains(node))
						continue;
					if (IsAccessible(information))
					{
						AStarPathNodeEntry entry = null;
						double cost = MovementCost(information);
						if (m_Entries.TryGetValue(node, out entry))
						{
							if (entry.Cost > cost)
							{
								entry.Cost = cost;
								entry.Path = information;
								entry.Origin = currentEntry;
							}
						}
						else
						{
							entry = new AStarPathNodeEntry(currentEntry, information, node, cost, EstimatedMovementCost(node, condition));
							m_OpenList.Add(entry);
							m_Entries.Add(node, entry);
						}
					}
				}
			}

			if (endEntry != null)
			{
				List<PathInformation> path = new List<PathInformation>();
				while (endEntry != null && endEntry.Path != null)
				{
					path.Add(endEntry.Path);
					endEntry = endEntry.Origin;
				}
				return path;
			}
			return null;
		}

		protected abstract bool IsAccessible(PathInformation path);
		protected abstract double EstimatedMovementCost(PathNode node, PathNodeCondition condition);
		protected abstract double MovementCost(PathInformation path);
	}
}
